//给定一个含有 n 个正整数的数组和一个正整数 target 。 
//
// 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长
//度。如果不存在符合条件的子数组，返回 0 。 
//
// 
//
// 示例 1： 
//
// 
//输入：target = 7, nums = [2,3,1,2,4,3]
//输出：2
//解释：子数组 [4,3] 是该条件下的长度最小的子数组。
// 
//
// 示例 2： 
//
// 
//输入：target = 4, nums = [1,4,4]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：target = 11, nums = [1,1,1,1,1,1,1,1]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 1 <= target <= 109 
// 1 <= nums.length <= 105 
// 1 <= nums[i] <= 105 
// 
//
// 
//
// 进阶： 
//
// 
// 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。 
// 
// Related Topics 数组 二分查找 前缀和 滑动窗口 
// 👍 842 👎 0

package leetcode.editor.cn;
/**
 * [209]长度最小的子数组
 */
public class MinimumSizeSubarraySum {
    public static void main(String[] args) {
        Solution solution = new MinimumSizeSubarraySum().new Solution();
        int length = 0;
//        int[] nums = new int[]{2,3,1,2,4,3};
//        length = solution.minSubArrayLen(7, nums);
//        if (length != 2) {
//            System.out.println("--1--");
//        }
//
//        int[] nums2 = new int[]{1,4,4};
//        length = solution.minSubArrayLen(4, nums2);
//        if (length != 1) {
//            System.out.println("--2--");
//        }

        int[] nums3 = new int[]{1,2,3,4,5};
        length = solution.minSubArrayLen(11, nums3);
        if (length != 3) {
            System.out.println("--3--");
        }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    // 个人代码
    public int minSubArrayLen2(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int sum = nums[0];
        int pre = 0, next = 0;
        while (true) {
            if (sum >= target) {
                int length = next - pre + 1;
                if (length < minLength) {
                    minLength = length;
                }
            }

            if (sum < target) {
                next++;
                if (next < nums.length) {
                    sum += nums[next];
                } else {
                    break;
                }
            } else {
                if (pre < next) {
                    sum -= nums[pre];
                    pre++;
                } else {
                    next++;
                    if (next < nums.length) {
                        sum += nums[next];
                    } else {
                        break;
                    }
                }
            }
        }
        if (minLength == Integer.MAX_VALUE) {
            return 0;
        }
        return minLength;
    }

    // 优化
    public int minSubArrayLen3(int target, int[] nums) {
        int minLength = Integer.MAX_VALUE;
        int sum = nums[0];
        int pre = 0, next = 0;
        while (true) {
            if (sum >= target) {
                int length = next - pre + 1;
                if (length < minLength) {
                    minLength = length;
                }
            }

            if (sum < target) {
                next++;
                if (next < nums.length) {
                    sum += nums[next];
                } else {
                    break;
                }
            } else {
                if (pre < next) {
                    sum -= nums[pre];
                    pre++;
                } else {
                    next++;
                    if (next < nums.length) {
                        sum += nums[next];
                    } else {
                        break;
                    }
                }
            }
        }
        if (minLength == Integer.MAX_VALUE) {
            return 0;
        }
        return minLength;
    }

    // 网友优化
    public int minSubArrayLen(int s, int[] nums) {
        int i = 0;
        int sum = 0;
        int len = 0;
        for (int j = 0; j < nums.length; j++) {
            sum += nums[j];
            while (sum >= s) {
                len = len == 0 ? j - i + 1 : Math.min(len, j - i + 1);
                sum -= nums[i++];
            }
        }
        return len;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}